原题地址：全排列 II
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
[1,1,2],
[1,2,1],
[2,1,1]
]
逐字插入
与 前一题 基本一致，只是因为数字可能重复，所以最后的排列需要去重：
/**
* @param {number[]} nums
* @return {number[][]}
*/
const permuteUnique1 = function(nums) {
let result = [[nums[0]]]; // 一个数字的排列只有一种
for (let i = 1; i < nums.length; i ++) {
let array = [];
for (let j = 0; j < result.length; j ++) {
for (let k = 0; k <= i; k ++) {
// 对前面数字的每一种排列，将当前数字插入到这些排列中的每一个位置
let temp = [...result[j]];
temp.splice(k,0,nums[i]);
array.push(temp);
}
}
result = array;
}
// 利用set去重
return [...new Set(...[result.map(item => item.join(','))])].map(item => item.split(',').map(str => Number(str)));
};
测试：
let start = new Date();
const test = permuteUnique1;
console.log(test([1,1,2])); // [ [ 2, 1, 1 ], [ 1, 2, 1 ], [ 1, 1, 2 ] ]
console.log(new Date().getTime() - start.getTime()); // 9
时间复杂度： 时间复杂度为$O(N!)$
空间复杂度： 最坏情况下没有重复数字，空间复杂度为$O(N!)$
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Aug 13,2019